package org.myy.learn.hot.finish.普通数组;

public class 最大子数组和 {
    //时间复杂度O(n)，空间复杂的O(n)
//    public int maxSubArray(int[] nums) {
//        int n = nums.length;
//        int[] perfix = new int[n];  //前缀和
//        perfix[0] = nums[0];
//        for (int i=1; i<n; i++){
//            int curMax = Math.max(perfix[i-1]+nums[i], nums[i]);
//            perfix[i] = curMax;
//        }
//        int max = Integer.MIN_VALUE;   //还有负数
//        for (int p : perfix){
//            int curmax = Math.max(p, max);
//            max = curmax;
//        }
//        return max;
//    }

    public int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];      // ① 全局最优值：到目前为止看见过的最大子数组和
        int maxEndingHere = nums[0]; // ② 局部最优值：必须以当前元素结尾的最大子数组和

        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            // ③ 决策：把 nums[i] 接在前一段后面，还是单独从 nums[i] 重新开始一段

            maxSoFar = Math.max(maxSoFar, maxEndingHere);
            // ④ 更新全局最优：要不要把“以 i 结尾的这一段”记为历史最佳
        }
        return maxSoFar; // ⑤ 遍历完整个数组后，真正的最大子数组和
    }
}
